package osSRC.fit;

import osSRC.Format;

import java.util.LinkedList;

public class Memory {
	static final int DEFAULT_MEMORY_LENGTH=1024*32;
	int length;
	LinkedList<Area> freeAreas,orderedFreeAreaQueue;
	Memory(){this(DEFAULT_MEMORY_LENGTH);}
	Memory(int length){
		this.length=length;
		freeAreas=new LinkedList<>();
		freeAreas.add(new Area(0,length));
	}
	boolean addressIsFree(int address){
		for(Area area:freeAreas){
			if(address>=area.getAddress()
			&&address<area.getAddress()
				+area.getLength())return true;
		}
		return false;
	}
	void orderFreeAreas(){
		Area area;
		LinkedList<Area> stack;
		orderedFreeAreaQueue=new LinkedList<>();
		System.gc();
		if(freeAreas.isEmpty())return;
		stack = new LinkedList<>(freeAreas);
		while (!stack.isEmpty()){
			area=stack.getFirst();
			for(Area temp:stack)
				if(temp.getLength()<area.getLength())
					area=temp;
			orderedFreeAreaQueue.add(area);
			stack.remove(area);
		}
	}
	void showAreas(boolean ordered){
		LinkedList<Area> linkedList;
		int index=0;
		if(freeAreas.isEmpty()){
			System.out.println("No free areas to show");
			return;
		}
		System.out.println("Free areas:");
		if(ordered){
			orderFreeAreas();
			for (Area area:orderedFreeAreaQueue)	System.out.println("\t"+(++index)+"\t"+area);
		}
		else for (Area area:freeAreas)				System.out.println("\t"+(++index)+"\t"+area);
	}
	int thisOrder(Area left, Area right){
		if		(left==null	||	right==null)	return 2;
		if		(left.getAddress()+ left.getLength()==right.getAddress())	return 1;
		else if	(left.getAddress()+ left.getLength()< right.getAddress())	return 0;
		else 																return 2;
	}
	boolean firstFit(int size){
		for(Area area:freeAreas){
			switch (area.allocate(size)){
				case 1:return true;
				case 0:freeAreas.remove(area);return true;
			}
		}
		return false;
	}
	boolean bestFit(int size){
		for(Area area:orderedFreeAreaQueue)
			if (area.getLength()>=size){
				switch (area.allocate(size)){
					case 1:return true;
					case 0:freeAreas.remove(area);return true;
				}
			}
		return false;
	}
	boolean free(int startAddress, int length){
		Area areaToBeFreed,newArea,
				left=null,right=null;
		int index;

		//judge whether the area is out of index
		if(startAddress+length>this.length||startAddress<0){
			System.out.println((startAddress+length)+":Invalid address");
			return false;
		}

		//judge whether the area is already freed
		for (int address=startAddress;address<startAddress+length;address++){
			if(addressIsFree(address)){
				System.out.println("Address"+address+"already freed");
				return false;
			}
		}

		//pre-check
		areaToBeFreed=new Area(startAddress,length);

		if(freeAreas.isEmpty()){
			freeAreas.add(new Area(startAddress,length));
			return true;
		}

		if(areaToBeFreed.getAddress()<freeAreas.getFirst().getAddress()){
				index=0;
				left=null;					right=freeAreas.getFirst();
		}
		else if(areaToBeFreed.getAddress()>freeAreas.getLast().getAddress()){
				index=freeAreas.size()-1;
				left=freeAreas.getLast();	right=null;
		}
		else for(index=0;index<=freeAreas.size()-2;index++)
			if(		areaToBeFreed.getAddress()>freeAreas.get(index).getAddress()
				&&	areaToBeFreed.getAddress()<freeAreas.get(index+1).getAddress()
			){
				left=freeAreas.get(index);	right=freeAreas.get(index+1);
				break;
			}
		//judge whether there are any existing free areas to merge
		if(thisOrder(left,areaToBeFreed)==1
			&&thisOrder(areaToBeFreed,right)==1){
			newArea=new Area(left.getAddress(),
					left.getLength()+length+right.getLength()
				);
				freeAreas.remove(left);	freeAreas.remove(right);
				freeAreas.add(index,newArea);
		}
		else if(thisOrder(left,areaToBeFreed)==1){
			newArea=new Area(left.getAddress(),
					left.getLength()+areaToBeFreed.getLength()
				);
				freeAreas.remove(index);
				freeAreas.add(index,newArea);
		}
		else if (thisOrder(areaToBeFreed,right)==1){
			newArea=new Area(areaToBeFreed.getAddress(),
					areaToBeFreed.getLength()+right.getLength()
				);
				freeAreas.remove(right);
				freeAreas.add(++index,newArea);
		}
		else	freeAreas.add(++index,areaToBeFreed);

		return true;
	}
	boolean requestArea(){
		int choice;
		String[] strategy={
				"""
Allocate Areas
1.first fit""",
				"2.best fit",
//				"3.worst fit",
				"0.return to last menu"
		};
		while (true) {
			showAreas(false);
			choice = Format.selectMenu(strategy, Main.scanner);
			switch (choice) {
				case 1:
					showAreas(false);
					if(!this.firstFit(Format.getInt(
							"Please Enter the Size you want to request:",
							Main.scanner)))return false;
					break;
				case 2:
					showAreas(true);
					if(!this.bestFit(Format.getInt(
							"Please Enter the Size you want to request:",
							Main.scanner)))return false;
					break;
				case 0:return true;
			}
		}
	}
}

